package chixing.day03;

import java.util.Arrays;

/*
* 数组：作用 存储数据
* 排序 sort
*
* （1）冒泡排序********
* （2）选择排序
* （3）插入排序
* （4）快速排序********
* （5）归并排序
* */
public class SortDemo {
    public static void main(String[] args) {

        int[] a = {61,19,56,37,20 ,66,50,34,37,3 };
//        a = SortDemo.bubboSort(a);
//        System.out.println(Arrays.toString(a));
//        a = SortDemo.selectSort(a);
//        System.out.println(Arrays.toString(a));
        a=SortDemo.quirckSort(a);
        System.out.println(Arrays.toString(a));
    }

    /**
     * 冒泡排序
     * 原理：相邻元素两两比较顺序
     * @param a 要排序的数组
     * @return
     */
    public static int[] bubboSort(int[] a){
        int temp;
        //循环n-1次，最后一次因为后面都拍序好了所以最小的一个就在他改在的位置所以省略最后一次循环
        for (int i=0;i<a.length-1;i++){
            //j<长度-i-1 因为是要跟他下一个作比较，要防止下标超限所以-1
            for (int j=0;j<a.length-i-1;j++){
                if (a[j]>a[j+1]){
                    temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                }
            }
        }
        return a;
    }

    /**
     * 选择排序
     * 遍历整个数组找到每次的最小值放到开始位置，便利n-1次,记住每个最小值的下标利用下彪进行交换
     * @param a 要排序的数组
     * @return
     */
//    int[] a = {61,19,56,37,20 ,66,50,34,37,3 };

    public static int[] selectSort(int[] a){
        //循环n-1次
        for (int i=0;i<a.length-1;i++){
            //假设最小的下标是i
            int min=i;
            //从下标为i的开始循环到最后
            for (int j=i;j<a.length;j++){
                //判断被遍历的数组中的最小值的下标放到min
                if (a[min]>a[j]){
                    min=j;
                }
            }
            //利用下标将最小值放到其实循环的位置
            int temp=a[i];
            a[i]=a[min];
            a[min]=temp;
        }
        return a;
    }

    /**
     * 插入排序
     * @param a 要排序的数组
     * @return
     */
    public static void insertSort(int[] a){
        int i;
        int j;
        int key;
    }

    /**
     * 快速排序
     * @param a
     * @return
     */
    public static int[] quirckSort(int[] a){
        if (a.length>2){
            quick(a,0,a.length-1);
        }
        return a;
    }
    public static void quick(int[] a,int low,int high){
        if (low<high){
            int middle = getMinddle(a,low,high);
            quick(a,low,middle-1);
            quick(a,middle+1,high);
        }
    }
    //每一趟排序，确定基数的下标（原数组分成左右两份）
    public static  int getMinddle(int[] a,int low,int high){
        //将a[low]设为基数开始比较
        int p = a[low];
        //当low==high是本次比较结束
        while (low<high){
            //基数与高位进行比较；若基数比高位小则
            while (low < high && p <= a[high]){
                high--;
            }
            a[low] = a[high];
            while (low < high && p >= a[low]){
                low++;
            }
            a[high] = a[low];
        }
        a[low] = p;
        return low;
    }




}
